#include "FindRepeatNumber.h"

static int f(std::vector<int> & nums, int first, int last){
	if(first <= last){
		const int m = (first + last) / 2;
		int val = (size_t)nums[m];
		if(val == m){
			int ret = f(nums, first, m-1);
			if(ret != -1) return ret;
			ret = f(nums, m + 1, last);
			if(ret != -1) return ret;
			return -1;
		}

		if(nums[val] == val){
			return val;
		}

		int tmp = nums[val];
		nums[val] = val;//put val in right place
		nums[m] = tmp;
		
		
		int ret = f(nums, first, val -1);
		if(ret != -1) return ret;

		ret = f(nums, val + 1, last);
		if(ret != -1) return ret;
	}
	return -1;
}

int FindRepeatNumber::findRepeatNumber(std::vector<int> & nums){
	return f(nums, 0, (int)(nums.size()-1));
}


void FindRepeatNumber::run(){
	{
		std::vector<int> vect = {2, 3, 1, 0, 2, 5, 3};
		int ret = findRepeatNumber(vect);
		//std::cout << "ret:" << ret << std::endl;
		assertTrue(2 == ret || ret == 3);
	}
	{
		std::vector<int> vect = {1, 1, 1};
		int ret = findRepeatNumber(vect);
		//std::cout << "ret:" << ret << std::endl;
		assertTrue(1 == ret);
	}
}
